package projet.metier;

import java.util.Collection;
import java.util.HashMap;
import edu.uci.ics.jung.graph.Graph;

/**
 * Allows to get the node with the best betweenness centrality of a graph given 
 * @author Rémi
 */
public class BetweennessCentrality {
	
	/**
	 * @param graph The graph
	 * @param ArrayNodes List of graph's nodes
	 * @param nbNodes Number of nodes
	 * @return Double array of Objects with the list of all ShortestPaths
	 */
	public static Object[][] getShortestPaths(Graph<String, Integer> graph, Object[] ArrayNodes, int nbNodes) {
		int v = 0;
		Object ShortCamino[][] = new Object[nbNodes*nbNodes][nbNodes];
		for (int i = 0 ; i < nbNodes ; i++) {
			// Get all the shortest paths for a node given
			HashMap<String, Object[]> resultsDijkstra = DijkstraAlgorithm.Dijkstra(graph, ArrayNodes[i].toString());
			for (int m = 0 ; m < nbNodes ; m++) {
				Object j = resultsDijkstra.get(ArrayNodes[m].toString())[1];
				int h = 0;
				if (j != null) {
					ShortCamino[v][h] = ArrayNodes[m].toString();
				}
				while (j != null) {
					ShortCamino[v][h+1] = j;
					j = resultsDijkstra.get(j)[1];
					h++;
				}
				v++;
			}
		}
		return ShortCamino;
	}
	
	/**
	 * 
	 * @param graph The graph
	 * @return String The name of the node with the highest betweenness centrality value
	 */
	public static String[] getBetweennessNodes(Graph<String, Integer> graph, int nbLocationsParcs) {
		// Get the number of vertex.
		int nbNodes = graph.getVertexCount();
		Collection<String> listNodes = graph.getVertices();
		Object[] ArrayNodes = listNodes.toArray();
		Object ShortCamino[][] = new Object[nbNodes*nbNodes][nbNodes];
		// Get all the shortest paths for a graph given with his nodes
		ShortCamino = BetweennessCentrality.getShortestPaths(graph, ArrayNodes, nbNodes);
		float[] CbusinneessResults = new float[nbNodes];
		HashMap<String, Float> CbusinneessNodes = new HashMap<String, Float>();
		// Brows all the nodes
		for (int j = 0 ; j < nbNodes ; j++) {
			int[] SumCaminoPassingBy = new int[nbNodes];
			int[] SumUsableCamino = new int[nbNodes];
			// Brows all the shortest paths
			for (int i = 0 ; i < nbNodes*nbNodes ; i++) {
				int g = 0;
				int sizeShortCamino = 0;
				while (ShortCamino[i][g] != null) {
					sizeShortCamino++;
					g++;
				}
				g = 0;
				// If the shortest path contains at least 2 nodes
				if (sizeShortCamino > 1) {
					boolean CaminoTidy = false;
					// If the shortest path do not begin by a node and do not finish by a node
					if (ShortCamino[i][0] != ArrayNodes[j] && ShortCamino[i][sizeShortCamino-1] != ArrayNodes[j]) {
						for (g = 0 ; g < sizeShortCamino ; g++) {
							// If the shortest path is passing by a node
							if (ShortCamino[i][g] == ArrayNodes[j] && ShortCamino[i][g] != null){
								CaminoTidy = true;
							} 
						}
						if (CaminoTidy) {
							// Sum of the shortest paths passing by node
							SumCaminoPassingBy[j]++;
						}
						else {
							// Sum of the shortest paths usable
							SumUsableCamino[j]++;
						}
					}
				}
			}
			// Calculation of the betweenness centrality
			CbusinneessResults[j] = new Float(SumCaminoPassingBy[j]) / new Float(SumUsableCamino[j]);
			
			CbusinneessNodes.put(ArrayNodes[j].toString(), CbusinneessResults[j]);
		}
		String bestKeys[] = new String[nbLocationsParcs];
		// Get max values of the hashmap
		for(int i = 0; i < nbLocationsParcs; i++){
			Object[] o = Location.GetMaxValue(CbusinneessNodes);
			bestKeys[i] = (String) o[0];
		}
		// Return the nodes with the best betweenness centrality
		return bestKeys;
	}
}
